
//1162.地图分析
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n=grid.size();
        int dx[]={1,-1,0,0};
        int dy[]={0,0,-1,1};

        queue<pair<int,int>> q;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        if(grid[i][j]==1) q.push({i,j});  //将陆地全部入队列

        int ret=-1,step=0;
        vector<vector<int>> vist(n,vector<int>(n));
        while(!q.empty())    //进行BFS
        {
            int _size=q.size();
            step++;
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<n&&!grid[a][b]&&!vist[a][b])
                    {
                       ret=max(ret,step);  //更新答案
                       vist[a][b]=step;     //对该位置进行标记
                       q.push({a,b});         //入队列,为下一次扩展做准备
                    }
                }
            }
        }        
        return ret;    
    }
};